package com.wtgroup.demo.leetcode.q010_正则表达式匹配;

import org.junit.Test;

/**
 * @author 60906
 * @date 2021/5/24 12:18
 */
public class Q010 {

    @Test
    public void test1() {
        // String s = "aab", p = "c*a*b";
        // String s = "mississippi", p = "mis*is*p*.";
        String s = "a", p = "ab*";
        boolean res = new Solution_T1().isMatch(s, p);
        System.out.println(res);
        boolean res2 = new Solution_T2().isMatch(s, p);
        System.out.println(res2);
    }


    /**
     * 递归尝试
     *
     * 效率: 42ms, 15%
     *
     * Q: 动归必要性? 重复子问题怎么理解?
     */
    class Solution_T1 {
        /*
        * 递归, 每次只处理单个字符. a* 尝试 0~N 个消耗; . 一个任意字符.
        * */

        public boolean isMatch(String s, String p) {
            if (s.isEmpty() && p.isEmpty()) {
                return true;
            }
            if (p.isEmpty()) {
                return false;
            }

            return func(s, p, 0, 0);
        }

        private boolean func(String s, String p, int sIndex, int pIndex) {
            // 两者同时结束
            if (sIndex == s.length() && pIndex == p.length()) {
                return true;
            }
            // s 不够或 p 不够 --> s 没有了, p 还有不一定 false , 比如p剩下x*
            if (/*sIndex == s.length() || */pIndex == p.length()) { // 暗含: sIndex != s.length()
                return false;
            }

            char currPat = p.charAt(pIndex);
            boolean isStar = false;
            if (pIndex < p.length() - 1 && p.charAt(pIndex + 1) == '*') {
                // 遇到 *, 一个不消耗~最大消耗尝试
                isStar = true;
            }
            boolean ans = false;
            if (isStar) {
                // 一个不消耗
                ans = func(s, p, sIndex, pIndex + 2);
            }

            if (!ans) {
                int end = isStar ? s.length() : Math.min(s.length(), sIndex + 1);
                for (int i = sIndex; i < end; i++) {
                    char currStr = s.charAt(i);
                    // 本次匹配, 才进入递归, 后面告诉我 true/false
                    // 不匹配, 后面不用看了
                    boolean f = currPat == '.' ? true : currPat == currStr;
                    if (!f) {
                        return false;
                    }

                    if (func(s, p, i + 1, pIndex + (isStar ? 2 : 1))) {
                        return true; // 当前匹配 & 后面也匹配 => 全局匹配成功.
                    }
                }
            }

            return ans;
        }
    }

    /**
     * 改成动归: 5ms, 63%
     *
     * todo 简化状态转移
     */
    class Solution_T2 {
        /*
         * 递归, 每次只处理单个字符. a* 尝试 0~N 个消耗; . 一个任意字符.
         * */

        public boolean isMatch(String s, String p) {
            if (s.isEmpty() && p.isEmpty()) {
                return true;
            }
            if (p.isEmpty()) {
                return false;
            }

            return func(s, p) == 1;
        }

        private int func(String s, String p) {
            int N = s.length(), M = p.length();
            int[][] dp = new int[N + 1][M + 1];


            // 两者同时结束
            dp[N][M] = 1;


            // p 没有了, 最后一列, 除了 [N][M] 都是0
            // s 没有了, p 还有不一定 false , 比如p剩下x*

            // 普遍位置, 从右到左, 从下到上
            for (int pIndex = M - 1; pIndex >= 0; pIndex--) {
                for (int sIndex = N; sIndex >=0; sIndex--) {
                    char currPat = p.charAt(pIndex);
                    boolean isStar = false;
                    if (pIndex < M - 1 && p.charAt(pIndex + 1) == '*') {
                        dp[sIndex][pIndex] = dp[sIndex][pIndex + 2]; // 一个不消耗
                        // 遇到 *, 一个不消耗~最大消耗尝试
                        if (dp[sIndex][pIndex] == 0) {
                            for (int i = sIndex; i < N; i++) {
                                char currStr = s.charAt(i);
                                // 本次匹配, 才进入递归, 后面告诉我 true/false
                                // 不匹配, 后面不用看了
                                boolean f = currPat == '.' ? true : currPat == currStr;
                                if (!f) {
                                    break;
                                }

                                // 往下看, 直到遇到 1 , 一直没有, 当前就是0
                                if (dp[i+1][pIndex + 2] == 1) {
                                    dp[sIndex][pIndex] = 1; // 当前匹配 & 后面也匹配 => 全局匹配成功.
                                    break;
                                }
                            }
                        }
                    } else {
                        if(sIndex==N) continue;
                        char currStr = s.charAt(sIndex);
                        boolean f = currPat == '.' ? true : currPat == currStr;
                        // 当前匹配 且 后面匹配 => 1
                        if (f && dp[sIndex + 1][pIndex + 1] == 1) {
                            dp[sIndex][pIndex] = 1; // 当前匹配 & 后面也匹配 => 全局匹配成功.
                        }
                    }
                }
            }

            return dp[0][0];
        }
    }



}
